1. Field of the Invention
The invention described herein is directed to detecting the unauthorized copying of multimedia content by recognition of a previously embedded fingerprint extracted from the digital data comprising the content. More specifically, the invention is directed to exploiting the interaction between the structure of a fingerprint code and the embedding of such code into multimedia content so that the embedded code can be used to identify one of a plurality of colluders of attempting to degrade the code's usability.
2. Brief Description of the Prior Art
Advancements in technology have made multimedia content easy to distribute for presentation. However, the ease with which multimedia content is distributed brings with it access by unauthorized users desiring to duplicate and redistribute it. In that protection of the content owner's property rights is essential to the content owner's financial bottom line, digital fingerprinting technology is being applied protect multimedia content from unauthorized dissemination. Fingerprinting digitally embeds a unique ID assigned to an authorized user into her copy of the content. The ID can be extracted from the content to help identify the originally assigned user of a suspicious copy when one is found or to prevent the presentation of the content if a fingerprint cannot be authenticated. In order to frustrate the detection of the embedded ID, however, groups of users collude to combine their respective copies of the content so as to generate an adulterated version having an altered fingerprint (referred to herein as a “colluded” copy). In this way, the colluding attackers protect their identities to avoid prosecution of infringement and other crimes. A fingerprinting system is considered collusion resistant when there is a high probability that one or more of the colluders can be positively identified from a suspicious copy of the fingerprinted multimedia content.
A growing number of collusion-resistant fingerprinting techniques have been recently implemented on multimedia. The most used methods fall mainly into one of two categories according to whether explicit discrete coding is involved. A typical example of non-coded fingerprinting is orthogonal fingerprinting, which assigns each user a spread spectrum sequence as a fingerprint. Each fingerprint sequence is typically orthogonal to the fingerprints of other users. The resistance to collusion by orthogonal fingerprinting is often improved by grouping together fingerprint sequences according to characteristics of users who are likely to collude together. However, while non-coded fingerprinting is easy to implement, the number of basis sequences required for its implementation and the computational complexity of detection increase linearly with the number of users assigned fingerprints.
Coded fingerprints take advantage of code modulation spread spectrum techniques and have been applied in the past to generic data, such as executable software programs and bitstreams. Prior art coding applications operated under a “marking assumption”, which was introduced by Boneh and Shaw in “Collusion-secure Fingerprinting for Digital Data”, IEEE Trans. on Information Theory, 44(5) pp. 1897-1905, 1998. The marking assumption assumes that colluders change only those fingerprint symbols in the colluders' corresponding codes that have different values. It is further assumed that the colluders assemble pieces of their codes that are different from the codes of other colluders in order to generate a new untraceable version. Numerous fingerprinting schemes have been developed base on the marking assumption to expand upon Boneh and Shaw's framework. For example, the “traceability (TA) code” may be constructed from structures resembling error correcting codes (ECC) and have been widely studied. Efficient decoding exists for some ECC, which makes such codes attractive for coded fingerprinting applications. As used herein, the coded fingerprinting scheme constructed under ECC principles will be referred to as “ECC based fingerprinting”.
Referring to FIG. 1, there is illustrated a framework for coded fingerprinting in accordance with ECC based fingerprinting of the prior art. As is shown in the Figure, the ECC based fingerprinting system includes an ECC based coding layer 100 and a spread spectrum based embedding layer 190. The layers respectively occupy the fingerprinting stage 105, where the fingerprints are applied to the multimedia content 135, and a detection stage 195, where the fingerprint codes are acquired from a test copy 150 of the content. The two stages are coupled by a distribution channel 145, which may be a telecommunications channel or may be a market channel through which hard storage copy of the content, such as by a compact disk (CD) or digital versatile disk (DVD), is physically carried. One or more attackers 140 obtain the content somewhere along the distribution channel 145 to carry out the attack.
In the system of FIG. 1, each authorized user of the content is assigned a codeword, which is formed from ECC symbols selected from an alphabet of size q and having a large minimum distance. The encoder 110 partitions the content into a plurality of non-overlapped segments and encodes one symbol of the codeword in each segment. The partition can be made spatially into blocks for image, or temporally into frames for video and audio. The symbol is encoded as one of q mutually orthogonal spread spectrum sequences with identical energy via modulator 120. Embedder 130 adds the sequence corresponding to the symbol value to the host signal at the appropriate segment. The embedder 130 may add the sequences in accordance with perceptual scaling known in the art so that the fingerprint will be unnoticed during presentation of the multimedia content.
The fingerprinted multimedia content 135 is presented to the distribution channel 145 where it may be subject to an attack by one or more attackers 140. Suspicious multimedia content 150 is the presented to an extractor 160 which retrieves the spread spectrum sequence from the content. The sequence is demodulated by demodulator 170 to retrieve the code and decoder 180 returns the user ID corresponding to the assigned fingerprint code.
Most prior art systems have only considered the coding layer and justify minimizing the impact of embedding by reliance on marking assumptions. However, the distortions and attacks mounted by adversaries on fingerprinted multimedia can lead to errors in detecting fingerprint code symbols which are not accounted for by marking assumptions.
Previous research has given preference to ECC based fingerprinting over the orthogonal non-coded approach because some classes of ECC have more efficient decoding algorithms than the maximum likelihood decoding that is commonly used for orthogonal fingerprinting. However, while efficient decoding does improve the detecting efficiency, it only provides a relatively small improvement in computational complexity. The major improvement on the detecting efficiency actually comes from the demodulation process.
One way in which an attack is carried out is by “interleaving collusion”, which is illustrated in FIG. 2, by which colluders contribute their assigned copies of the content segment by segment (or equivalently, symbol by symbol at the code level) with approximately equal share. A codeword for a user 1 was originally taken from codebook 210 and an ECC based codeword 220 was built thereon. A codeword 230 for user 2 was similarly constructed. Each colluding user 220, 230 then provides roughly an equal number of segments containing their corresponding symbols to a colluded version 240. Further distortion may be applied on the colluded signal, which is modeled as additive white Gaussian noise 250. At the detector side, the colluded codeword 260 is first extracted by demodulating symbols from each segment. The colluder is then identified by, for example, matching the extracted codeword with an entry in the codebook.
In another well-known type of collusion of collusion attack, the participants linearly combine their copies of the multimedia content to produce a colluded version. This generally reduces the energy in each contributed fingerprint until it is no longer discernible. Such collusion attacks are referred to herein as “averaging collusion” attacks.
An analytical approximation of the probability of detecting a single colluder, Pd, for the ECC based fingerprinting under interleaving and averaging collusion is graphically illustrated in FIG. 3A and FIG. 3B, respectively. The Watermark-to-Noise-Ratio (WNR) ranges from 0 dB to −20 dB, which includes the scenarios of severe distortion to mild distortion. The orthogonal fingerprinting case is shown in FIG. 3C and FIG. 3D for interleaving collusion and averaging collusion, respectively. Comparing the results of FIGS. 3B and 3D show that under averaging collusion, the orthogonal fingerprinting and ECC based fingerprinting constructed above have similar performance. They both resist at least a few dozens colluders' averaging attack under high WNR and about half dozen under low WNR. Thus, from colluders' point of view, averaging collusion for an ECC based fingerprinting system is not a very effective strategy. However, under interleaving collusion, as shown in FIG. 3A and FIG. 3C, a huge gap in the collusion resistance between the two systems is clearly shown. For orthogonal fingerprinting, the probability of colluder detection under interleaving collusion is the same as that under averaging collusion owing to the orthogonal spreading. At WNR=0 dB, the Pd remains close to 1 when c is a few dozen and still near 0.9 even when c is as high as 140. On the other hand, the detection probability of the ECC based fingerprinting drops sharply when more than 6-7 colluders are involved in creating an interleaved copy, even when WNR is high. Thus, from the colluders' point of view, interleaving collusion is an effective strategy to circumvent the protection.
Careful examination of the two types of collusion shows that the difference in the resistance against them is derived from the role given to the embedding layer. The segment-wise interleaving collusion is equivalent to the symbol-wise interleaving collusion on the code level since each colluded segment comes from just one user. The collusion resilience primarily relies on what is provided by the code layer and bypasses the embedding layer. Because of the limited alphabet size, the chance of the colluders to interleave their symbols and create a colluded fingerprint close to the fingerprint of an innocent user is so high that if to handle this on the code level alone, it would require a large minimum distance in the code design. This means that either a code representing some given number of users can resist only a small number of colluders, or a code can represent only a small total number of users. On the other hand, for averaging collusion, every colluder contributes his/her share in every segment. Through a correlation detector, the collection of such contribution over the entire test signal leads to high expected correlation values when correlating with the fingerprints from the true colluders, and to low expected correlation when the fingerprints from innocent users. In other words, the embedding layer contributes to defending the collusion. This suggests that more closely considering the relation between fingerprint encoding, embedding, and detection is helpful to improve the collusion resistance against interleaving collusion.
When designing a fingerprinting system, a better trade-off between the collusion resistance and other performance measures such as detection computational complexity is desired. Although the orthogonal fingerprinting performs well in collusion resistance, its detection computational complexity and distribution cost are inhibiting. However, the significant computational advantages of ECC based fingerprinting provide motivation to find avenues to improve the collusion resistance of ECC based fingerprinting so as to reduce the performance gap between the ECC based and orthogonal fingerprinting while preserving its efficient detection and distribution.